# LeetCode 684、冗余连接
# 一、题目描述
树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。
示例 1：
img
输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]
示例 2：
img
输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
提示:
n == edges.length3 <= n <= 1000edges[i].length == 21 <= ai < bi <= edges.lengthai != biedges中无重复元素- 给定的图是连通的
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：278166530
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
// 创建二维数组表示单边数组
List<List<Integer>> graph;
// 记录从某个点出发开始访问时，每个节点是否被访问
List<Boolean> visited;
// 当前是否找到环
boolean hasCycle = false;
public int[] findRedundantConnection(int[][] edges) {
// n 个节点，节点值在 1 ~ n
int n = edges.length;
// 初始化图，由于节点值在 1 ~ n，所以二维矩阵的大小为 n + 1
// 即索引为 0 的那一行不会记录数据
graph = new ArrayList<List<Integer>>(n + 1);
// 初始化每一行
// 每一行记录一个节点的信息
for (int i = 0; i <= n; i++) {
// 使用数组进行记录
graph.add(new ArrayList<Integer>());
}
// 访问 edges
for (int[] edge : edges) {
// 每一个 edge 都包含了两个节点的信息
// 由于是无向图，所以两者都可以相互访问到对方
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
// 每增一条 edge 边，在原来的已经访问节点的基础上看这条边是否形成了环
hasCycle = false;
// 重新初始化 visited
visited = new ArrayList<Boolean>();
// 默认都是 false
for (int i = 0; i <= n; i++) {
visited.add(false);
}
// 开始以 edge[0] 这个节点作为初始节点进行访问
// 既然以它作为初始节点，那么它的父节点就是不存在的，用 -1 来表示
dfs(edge[0], -1);
// 如果在访问结束后发现找到了环
if(hasCycle){
// 那么 edge 就是最后出现的边
return edge;
}
}
return null;
}
// 图深度优先遍历
// curNode ：出发节点
// fatherNode ： 出发节点的父节点
private void dfs(int curNode, int fatherNode) {
// curNode 这个节点被访问了，更新为 true
// visited 的索引值就是节点值
visited.set(curNode, true);
// 获取 curNode 可以前往的所有节点信息
List<Integer> info = graph.get(curNode);
// 对每个可以前往的节点都访问一下
for (int nextNode : info) {
// 如果发现是前往父节点，不处理，直接看下一个节点
if (nextNode == fatherNode)
continue;
// 如果发现 nextNode 是还未访问的节点
if (!visited.get(nextNode)) {
// 那么以 nextNode 作为初始节点，curNode 作为父节点
// 递归的进行搜索访问下去
dfs(nextNode, curNode);
// 否则，如果发现 nextNode 是已经访问过的节点
} else {
// 说明从 nextNode 经过一系列访问后来到了 curNode
// curNode 又能来到 nextNode
// 有环了
hasCycle = true;
return;
}
}
}
}
# **2、**C++ 代码
# 3、Python 代码
登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 微信：278166530
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution:
# 创建二维数组表示单边数组
graph = []
# 记录从某个点出发开始访问时，每个节点是否被访问
visited = []
# 当前是否找到环
hasCycle = False
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
# n 个节点，节点值在 1 ~ n
n = len(edges)
# 初始化图，由于节点值在 1 ~ n，所以二维矩阵的大小为 n + 1
# 即索引为 0 的那一行不会记录数据
# 初始化每一行
# 每一行记录一个节点的信息
self.graph = [[] for i in range( n + 1)]
# 访问 edges
for edge in edges :
# 每一个 edge 都包含了两个节点的信息
# 由于是无向图，所以两者都可以相互访问到对方
self.graph[edge[0]].append(edge[1])
self.graph[edge[1]].append(edge[0])
# 每增一条 edge 边，在原来的已经访问节点的基础上看这条边是否形成了环
self.hasCycle = False
# 重新初始化 visited
self.visited = [ False ] * (n + 1)
# 默认都是 false
# 开始以 edge[0] 这个节点作为初始节点进行访问
# 既然以它作为初始节点，那么它的父节点就是不存在的，用 -1 来表示
self.dfs(edge[0], -1)
# 如果在访问结束后发现找到了环
if self.hasCycle :
# 那么 edge 就是最后出现的边
return edge
# 图深度优先遍历
# curNode ：出发节点
# fatherNode ： 出发节点的父节点
def dfs(self,curNode, fatherNode) :
# curNode 这个节点被访问了，更新为 true
# visited 的索引值就是节点值
self.visited[curNode] = True
# 获取 curNode 可以前往的所有节点信息
# 对每个可以前往的节点都访问一
for nextNode in self.graph[curNode]:
# 如果发现是前往父节点，不处理，直接看下一个节点
if nextNode == fatherNode :
continue
# 如果发现 nextNode 是还未访问的节点
if self.visited[nextNode] == False:
# 那么以 nextNode 作为初始节点，curNode 作为父节点
# 递归的进行搜索访问下去
self.dfs(nextNode, curNode)
# 否则，如果发现 nextNode 是已经访问过的节点
else:
# 说明从 nextNode 经过一系列访问后来到了 curNode
# curNode 又能来到 nextNode
# 有环了
self.hasCycle = True
return